package SubjectTree.Three;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

import Utility.TreeNode;

public class SumOfLeftLeaves {

/**
 * 难度：简单
 * 
 * 404. 左叶子之和
 * 	计算给定二叉树的所有左叶子之和。
 * 	
 * 示例：
 * 	    3
 * 	   / \
 * 	  9  20
 * 	    /  \
 * 	   15   7
 * 	在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		SumOfLeftLeaves soll = new SumOfLeftLeaves();
		System.out.println(soll.sumOfLeftLeaves_1(TreeNode.MkTree("[3,9,20,null,null,15,7]")));
	}
	//自己写(逐层遍历)
	public int sumOfLeftLeaves(TreeNode root) {
		if(root==null)return 0;
		Deque<TreeNode> deque = new LinkedList<>();
		deque.push(root);
		int count = 0;
		while(!deque.isEmpty()) {
			int currentLevelSize = deque.size();
			for(int i=0;i<currentLevelSize;i++) {
				TreeNode node = deque.poll();
				if(node.left!=null) {
					deque.push(node.left);
					if(node.left.left==null && node.left.right ==null) {
						count+=node.left.val;
					}
				}
				if(node.right!=null)deque.push(node.right);
			}
		}
		return count;
    }
	//自己写(递归)
	public int sumOfLeftLeaves_1(TreeNode root) {
		if(root==null)return 0;
		int count = 0;
		if(root.left!=null) {
			if(root.left.left==null && root.left.right ==null) {
				count += root.left.val;
			}
		}
		count = sumOfLeftLeaves_1(root.left) + sumOfLeftLeaves_1(root.right) + count;
		return count;
    }
	//方法一：深度优先搜索
	public int sumOfLeftLeaves1(TreeNode root) {
        return root != null ? dfs(root) : 0;
    }
    public int dfs(TreeNode node) {
        int ans = 0;
        if (node.left != null) {
            ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);
        }
        if (node.right != null && !isLeafNode(node.right)) {
            ans += dfs(node.right);
        }
        return ans;
    }
    public boolean isLeafNode(TreeNode node) {
        return node.left == null && node.right == null;
    }
    //方法二：广度优先搜索
    public int sumOfLeftLeaves2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                if (isLeafNode(node.left)) {
                    ans += node.left.val;
                } else {
                    queue.offer(node.left);
                }
            }
            if (node.right != null) {
                if (!isLeafNode(node.right)) {
                    queue.offer(node.right);
                }
            }
        }
        return ans;
    }
}
